// https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/

// 题干：给你一个正整数数组 nums 。
//      每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。
//     （注意，在后续操作中你可以对减半过的数继续执行操作）
//      请你返回将 nums 数组和 至少 减少一半的 最少 操作数。

// 示例：输入：nums = [5,19,8,1]
//      输出：3

// 碎语：

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int halveArray(vector<int>& nums)
    {
        priority_queue<double> heap; // 默认大根堆
        double sum = 0.0;
        for (const auto& num : nums) {
            heap.push(num);
            sum += num;
        }

        sum /= 2.0;
        int count = 0;

        while (sum > 0){
            double t = heap.top() / 2.0;
            heap.pop();
            sum -= t;
            count++;
            heap.push(t);
        }


        return count;
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {5,19,8,1};

    cout << sol.halveArray(nums) << endl;

    return 0;
}